package offer_2._68_lowestCommonAncestor_2;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class lowestCommonAncestor {
    public TreeNode _lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归中止
        if (root == null)
            return null;
        // 递归中止2
        if (root == p || root == q)
            return root;

        // 递归
        TreeNode left = _lowestCommonAncestor(root.left, p, q);
        TreeNode right = _lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root; // 说名在root两端
        }
        if (left != null) {
            return left; // 说明p，q在left端
        }

        if (right != null) {
            return right; // 说明p,q在right端
        }
        return null;
    }
}
